// =================================================================
// Name: FSManager.cpp
// Desc: Contains implementations of functions in FSManager class
// =================================================================

// =================================================================
// INCLUDES
// =================================================================

#include <iostream>
#include <cmath>
#include <fstream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <sstream>
#include <algorithm>
#include <vector>
#include "Tokenize.h"
#include "FSManager.h"
#include "Inode.h"
#include "Superblock.h"
#include "IndirectBlock.h"
#include "commands.h"
#include "config.h"

using namespace std;

// =================================================================
// FUNCTIONS
// =================================================================

// =================================================================
// Name: FSManager::FSManager
// Desc: Instantiates the filesystem
// Args: string filename - file to store the filesystem in on disk
// =================================================================
FSManager::FSManager(string filename)
{
    // If filesystem does not exist, create file
	fp = fopen(filename.c_str(), "r+");
    if (fp == NULL)
    {
        fp = fopen(filename.c_str(), "w");
        fclose(fp);
        fp = fopen(filename.c_str(), "r+");
        mkfs(this);
    }
    // Otherwise read in data from file
	else{
        ReadSuperblock();
        root_dir = ReadDirectory("/");
        current_dir = root_dir;
    }
}

// =================================================================
// Name: FSManager::~FSManager
// Desc: Do cleanup on exit
// =================================================================
FSManager::~FSManager()
{
    // Dump data in memory to file
	WriteDirectory(root_dir);
    WriteDirectory(current_dir);
    WriteSuperblock();
    open_files.clear();
    cache.clear();
    fclose(fp);

    // Free up memory in use
	if (root_dir != current_dir) {
        if (root_dir != NULL)
            delete root_dir;
        if (current_dir != NULL)
            delete current_dir;
    }
    else {
        if (root_dir != NULL)
            delete root_dir;
    }
    delete sb;
}

// =================================================================
// Name: FSManager::Reset
// Desc: Resets the state of FSManager when mkfs is called
// =================================================================
void FSManager::Reset()
{
    // Free up all data in memory
	if (root_dir != current_dir) {
        if (root_dir != NULL)
            delete root_dir;
        if (current_dir != NULL)
            delete current_dir;
    }
    else {
        if (root_dir != NULL)
            delete root_dir;
    }
    delete sb;
    open_files.clear();
    cache.clear();
}

// =================================================================
// Name: FSManager::GetFP
// Desc: fp accessor function
// Rets: pointer to filesystem file
// =================================================================
FILE* FSManager::GetFP()
{
    return fp;
}

// =================================================================
// Name: FSManager::SetSB
// Desc: sb setter function
// Args: Superblock* sb - pointer to a Superblock to assign
// =================================================================
void FSManager::SetSB(Superblock *sb)
{
    this->sb = sb;
}

// =================================================================
// Name: FSManager::GetSB
// Desc: sb accessor function
// Rets: pointer to Superblock in use
// =================================================================
Superblock *FSManager::GetSB()
{
    return sb;
}

// =================================================================
// Name: FSManager::WriteDirectory
// Desc: Writes the contents of a directory
// Args: Directory* dir - pointer to directory to save
// =================================================================
void FSManager::WriteDirectory(Directory *dir) 
{
    // Convert the map in dir to a string
	stringstream data;

    map<string, int> entries = dir->GetEntries();
    map<string, int>::iterator it;

    // Iterate through the filename,inode map
	for (it = entries.begin(); it != entries.end(); it++) {
        data << it->first << "\t" << it->second << "\n";
    }
	
    // Write the contents of dir to file
	WriteFile(data.str(), dir, true);
}

// =================================================================
// Name: FSManager::InsertOpenFile
// Desc: Adds a new open file descriptor when open is called
// Args: int fd - the file descriptor
//       File* file - pointer to file to be accessed by fd
// =================================================================
void FSManager::InsertOpenFile(int fd, File *file)
{
    open_files.insert(pair<int,File*>(fd, file));
}

// =================================================================
// Name: FSManager::RemoveOpenFile
// Desc: Removes a open file descriptor from map when close called
// Args: int fd - file descriptor to close
// =================================================================
void FSManager::RemoveOpenFile(int fd)
{
    // If file desciptor exists in map, remove it
	map<int,File*>::iterator it;
    it = open_files.find(fd);

    if (it != open_files.end()) {
        delete it->second;
        open_files.erase(it);
    }
    else {
        cerr << "CAN NOT CLOSE UNOPENED FILE!!" << endl;
    }

}

// =================================================================
// Name: FSManager::UpdateLRU
// Desc: Sets priority of block in cache to top position when that
//       block is read or written to
// Args: int block_index - which block to update
// =================================================================
void FSManager::UpdateLRU(int block_index)
{
    vector<int>::iterator it;

    // Only update position if the block already exists in cache
	if(cache.find(block_index) != cache.end())
    {
        for(it = cache_lru.begin(); it != cache_lru.end(); it++)
        {
            if(block_index == *it)
            {
                cache_lru.erase(it);
                cache_lru.push_back(block_index);
            }
        }
    }
}

// =================================================================
// Name: FSManager::WriteCache
// Desc: Writes contents of a block to the cache
// Args: int block_index - block location to write
//       Block* block - contents of block to write
// =================================================================
void FSManager::WriteCache(int block_index, Block *block)
{
    map<int,Block*>::iterator it;

    it = cache.find(block_index);

    // If block is already in cache, update its priority and value
	if(it != cache.end())
    {
        cache[block_index] = block;
        UpdateLRU(block_index);
    }
	// Otherwise add it to the cache
    else
    {
        cache.insert(pair<int,Block*>(block_index,block));
        cache_lru.push_back(block_index);
        if(cache_lru.size()*BLOCK_SIZE > CACHE_SIZE)
        {
            int old_index = cache_lru[0];
            cache_lru.erase(cache_lru.begin());
            cache.erase(old_index);
        }
    }
}

// =================================================================
// Name: FSManager::ReadCache
// Desc: Reads a block from the cache and returns its contents
// Args: int block_index - location of block to read
// Rets: Block pointer containing contents of the block if it exists
//       or NULL if block is not in cache
// =================================================================
Block *FSManager::ReadCache(int block_index)
{

    // If block is in cache, update priority and return data
	if(cache.find(block_index) != cache.end())
    {
        UpdateLRU(block_index);
        return cache[block_index];
    }
    else
        return NULL;

}

// =================================================================
// Name: FSManager::GetNextAvailableFD
// Desc: Returns the next file descriptor which is not in use
// Rets: a file descriptor
// =================================================================
int FSManager::GetNextAvailableFD() 
{
    int i = 0;
    map<int,File*>::iterator it;

    // Increment i from 0 until a free file descriptor is found
	while (1) {
        it = open_files.find(i);
        if (it == open_files.end()) {
            return i;
        }
        else {
            i++;
        }
    }
}

// =================================================================
// Name: FSManager::GetOpenFile
// Desc: Returns pointer to file given a file descriptor
// Args: int fd - file descriptor of an open file
// Rets: pointer to a File object containing data corresponding to
//       fd or NULL if fd does not exist
// =================================================================
File *FSManager::GetOpenFile(int fd)
{
    map<int,File*>::iterator it;
    it = open_files.find(fd);

    if (it != open_files.end())
        return it->second;
    else
        return NULL;
}

// =================================================================
// Name: FSManager::GetCurrentDirectory
// Desc: current_dir accessor function
// Rets: pointer to Current Directory
// =================================================================
Directory* FSManager::GetCurrentDirectory()
{
    return current_dir;
}

// =================================================================
// Name: FSManager::SetCurrentDirectory
// Desc: current_dir setter function
// Args: Directory* dir - directory to set as current directory
// =================================================================
void FSManager::SetCurrentDirectory(Directory *dir)
{
    current_dir = dir;
}

// =================================================================
// Name: FSManager::GetRootDirectory
// Desc: root_dir accessor function
// Rets: pointer to Root Directory
// =================================================================
Directory* FSManager::GetRootDirectory()
{
    return root_dir;
}

// =================================================================
// Name: FSManager::SetRootDirectory
// Desc: root_dir setter function
// Args: Directory* dir - directory to set as root directory
// =================================================================
void FSManager::SetRootDirectory(Directory *dir)
{ 
    root_dir = dir;
}

// =================================================================
// Name: FSManager::ReadDirectory
// Desc: Returns a pointer to a directory given its filename
// Args: string path - filename of the directory to get contents of
// Rets: Pointer to Directory of specified file
// =================================================================
Directory* FSManager::ReadDirectory(string path) 
{


    vector<string> tokens;
    Tokenize (path, tokens, "/");
    int parent_inode, current_inode;
    Directory *working_dir;

    // Check for root
    if (tokens.empty())
    {
        parent_inode = 0;
        current_inode = 0;
        Inode *node = ReadInode(0);
        working_dir = new Directory(0, 0);
        string contents = ReadFile(working_dir, node->GetSize());

        // Parse the directory contents
        vector<string> dir_tokens;
        Tokenize(contents, dir_tokens, "\t\n");

        for (unsigned int i = 0; i < dir_tokens.size(); i+=2)
        {
            working_dir->InsertEntry(dir_tokens[i], atoi(dir_tokens[i+1].c_str()));
        }
        return working_dir;
    }

    // First char as '/' signifies absolute path
	if (path[0] == '/') {
        working_dir = root_dir;
    }
    else
    {
        working_dir = current_dir;
    }

    // Traverse the file path reading in each directory
	for (unsigned int i = 0; i < tokens.size(); i++)
    {
        parent_inode = working_dir->GetEntry("./");
        current_inode = working_dir->GetEntry(tokens[i] + "/");

        if (parent_inode == -1 || current_inode == -1)
        {
            cout << "Directory along path does not exist" << endl;
            exit(1);
        }

        if (working_dir != root_dir && working_dir != current_dir)
            delete working_dir;

        working_dir = new Directory(current_inode);
        Inode *node = ReadInode(current_inode);
        string contents = ReadFile(working_dir, node->GetSize());

        // Parse the directory contents
        vector<string> dir_tokens;
        Tokenize(contents, dir_tokens, "\t\n");

        for (unsigned int i = 0; i < dir_tokens.size(); i+=2)
        {
            working_dir->InsertEntry(dir_tokens[i], atoi(dir_tokens[i+1].c_str()));
        }

    }

    return working_dir;

}

// =================================================================
// Name: FSManager::WriteIndirectBlock
// Desc: Writes IndirectBlock addresses to specified block
// Args: IndirectBlock* block - contains addresses to data blocks
//       int index - block index to write addresses to
// =================================================================
void FSManager::WriteIndirectBlock(IndirectBlock *block, int index)
{
    // Calculate block location and write there
	int block_location = sb->GetBlocksOffset() + (index * BLOCK_SIZE);

    fseek(fp, block_location, SEEK_SET);

    fwrite((const void*)block->GetAddrs(), sizeof(int), BLOCK_SIZE/INT_SIZE, fp);

}

// =================================================================
// Name: FSManager::ReadIndirectBlock
// Desc: Reads in addresses to an IndirectBlock at a specified block
// Args: int index - block index to read addresses from
// Rets: IndirectBlock pointer containing data block addresses
// =================================================================
IndirectBlock* FSManager::ReadIndirectBlock(int index)
{
    IndirectBlock *block = new IndirectBlock();
    int addr[BLOCK_SIZE/INT_SIZE];

    // Calculate block location and read from there
	int block_location = sb->GetBlocksOffset() + (index * BLOCK_SIZE);

    fseek(fp, block_location, SEEK_SET);
    fread(addr, sizeof(int), BLOCK_SIZE/INT_SIZE, fp);

    for (int i = 0; i < BLOCK_SIZE/INT_SIZE; i++)
        block->SetAddr(i, addr[i]);

    return block;
}

// =================================================================
// Name: FSManager::WriteInode
// Desc: Writes the contents of an Inode to disk for specified inode
// Args: Inode* node - contents of inode to write
//       int index - inode location to store data
// =================================================================
void FSManager::WriteInode(Inode *node, int index)
{
    // Calculate inode location and write data there
	int inode_location = sb->GetInodesOffset() + (index * INODE_SIZE);

    fseek(fp, inode_location, SEEK_SET);

    int temp[6] = { node->GetSize(), 
        node->GetNumBlocks(),
        node->GetNumLinks(),
        node->GetAccessed(),
        node->GetModified(),
        node->GetChanged() };

    fwrite((const void*)&temp, sizeof(int), 6, fp);

    int *block_locations = node->GetBlockLocations();
    fwrite((const void *)block_locations, sizeof(int), NUM_BLOCK_LOCATIONS, fp);

}

// =================================================================
// Name: FSManager::ReadInode
// Desc: Reads contents of inode from disk and saves in an Inode
// Args: int index - location of inode to read
// Rets: Inode pointer containing Inode information read in
// =================================================================
Inode *FSManager::ReadInode(int index) 
{
    int temp[6];
    int temp2[NUM_BLOCK_LOCATIONS];

    // Calculate location of inode and read in data to Inode class
	int inode_location = sb->GetInodesOffset() + (index * INODE_SIZE);

    fseek(fp, inode_location, SEEK_SET);

    fread(temp, sizeof(int), 6, fp);
    fread(temp2, sizeof(int), NUM_BLOCK_LOCATIONS, fp);

    Inode *node = new Inode(temp[0], temp[1], temp[2], temp[3], temp[4], temp[5], temp2);

    return node;
}

// =================================================================
// Name: FSManager::WriteSuperblock
// Desc: Writes the contents of superblock to file
// =================================================================
void FSManager::WriteSuperblock()
{
    fseek(fp, 0, SEEK_SET);

    //NumDataBlocks InodesOffset and DataBlock Offset are computed in superblock constructor
    int temp[5] = { sb->GetFsSize(),
        sb->GetBlockSize(),
        sb->GetNumInodes(),
        sb->GetNumFreeInodes(),
        sb->GetNumFreeDataBlocks() };

    fwrite((const void*)&temp, sizeof(int), 5, fp);

    // Write each free inode in list
	for (int i = 0; i < sb->GetNumFreeInodes(); i++)
    {
        int value = sb->GetFreeInodeIndex(i);
        fwrite((const void*)&value, sizeof(int), 1, fp);
    }

    // Write each free data block in list
	for (int i = 0; i < sb->GetNumFreeDataBlocks(); i++)
    {
        int value = sb->GetFreeDataBlockIndex(i);
        fwrite((const void*)&value, sizeof(int), 1, fp);
    }
}

// =================================================================
// Name: FSManager::ReadSuperblock
// Desc: Reads in contents of superblock from file and saves in sb
// =================================================================
void FSManager::ReadSuperblock()
{
    int temp[5];
    int fs_size;
    int block_size;
    int num_inodes;
    int num_free_inodes;
    int num_free_data_blocks;

    fseek(fp,0,SEEK_SET);

    fread(temp,sizeof(int),5,fp);

    fs_size = temp[0];
    block_size = temp[1];
    num_inodes = temp[2];
    num_free_inodes = temp[3];
    num_free_data_blocks = temp[4];

    // Create new Superblock from bookkeeping parameters read in
	Superblock *sb = new Superblock(fs_size,block_size,num_inodes);  

    // Populate free inode list
	for(int i = 0; i < num_free_inodes; i++){
        int tmp[1];
        fread(tmp,sizeof(int),1,fp);
        sb->AddFreeInode(tmp[0]);
    }

    // Populate free data block list
	for(int i = 0; i < num_free_data_blocks; i++){
        int tmp[1];
        fread(tmp,sizeof(int),1,fp);
        sb->AddFreeDataBlock(tmp[0]);
    }

    this->sb = sb;
}

// =================================================================
// Name: FSManager::MakeSinglyIndirect
// Desc: Sets up Single Indirection for data blocks in inode
// Args: int index - data block index to create pointers in
//       int& num_blocks - number of data blocks to allocate
// Rets: index of data block in which Single Indirection is created
// =================================================================
int FSManager::MakeSinglyIndirect(int index, int &num_blocks)
{

    IndirectBlock *iBlock;

    // Grab a new data block for indirection if not allocated
	if (index == -1)
    {
        iBlock = new IndirectBlock();
        index = sb->FreeDataBlockPop();
    }
    else
    {
        iBlock = ReadIndirectBlock(index);
    }

    // Loop through singly indirect block allocating data blocks
    for (int i = 0; i < BLOCK_SIZE/INT_SIZE; i++)
    {

        if (iBlock->GetAddr(i) == -1)
        {
            iBlock->SetAddr(i, sb->FreeDataBlockPop());
        }
        num_blocks--;
        if (num_blocks == 0)
            break;
    }
	
	// Write the newly created IndirectBlock to file
    WriteIndirectBlock(iBlock, index);
    delete iBlock;

    return index;

}

// =================================================================
// Name: FSManager::MakeDoublyIndirect
// Desc: Sets up Double Indirection for data blocks in inode
// Args: int index - data block index to create pointers in
//       int& num_blocks - number of data blocks to allocate
// Rets: index of data block in which Double Indirection is created
// =================================================================
int FSManager::MakeDoublyIndirect(int index, int &num_blocks)
{
    IndirectBlock *iBlock;

    // Allocate new data block if not specified
	if (index == -1)
    {
        iBlock = new IndirectBlock();
        index = sb->FreeDataBlockPop();
    }
    else
    {
        iBlock = ReadIndirectBlock(index);
    }

    // Loop through doubly indirect block allocating data blocks
    for (int i = 0; i < BLOCK_SIZE/INT_SIZE; i++)
    {
        if (iBlock->GetAddr(i) == -1)
        {
            iBlock->SetAddr(i, sb->FreeDataBlockPop());
            IndirectBlock* emptyBlock = new IndirectBlock();
            WriteIndirectBlock(emptyBlock, iBlock->GetAddr(i));
            delete emptyBlock;
        }

        // Set up single indirection for each block address
		MakeSinglyIndirect(iBlock->GetAddr(i), num_blocks);
        if (num_blocks == 0)
            break;

    }

    // Write the newly created IndirectBlock to file
	WriteIndirectBlock(iBlock, index);
    delete iBlock;

    return index;
}

// =================================================================
// Name: FSManager::MakeTriplyIndirect
// Desc: Sets up Triple Indirection for data blocks in inode
// Args: int index - data block index to create pointers in
//       int& num_blocks - number of data blocks to allocate
// Rets: index of data block in which Triple Indirection is created
// =================================================================
int FSManager::MakeTriplyIndirect(int index, int &num_blocks)
{
    IndirectBlock *iBlock;

    // Allocate data block if not specified
	if (index == -1)
    {
        iBlock = new IndirectBlock();
        index = sb->FreeDataBlockPop();
    }
    else
    {
        iBlock = ReadIndirectBlock(index);
    }

    // Loop through triply indirect block allocating data blocks
    for (int i = 0; i < BLOCK_SIZE/INT_SIZE; i++)
    {
        if (iBlock->GetAddr(i) == -1)
        {
            iBlock->SetAddr(i, sb->FreeDataBlockPop());
            IndirectBlock* emptyBlock = new IndirectBlock();
            WriteIndirectBlock(emptyBlock, iBlock->GetAddr(i));
            delete emptyBlock;
        }

        // For each address, setup double indirection
		MakeDoublyIndirect(iBlock->GetAddr(i), num_blocks);
        if (num_blocks == 0)
            break;

    }
	
	// Write the newly created IndirectBlock to file
    WriteIndirectBlock(iBlock, index);
    delete iBlock;

    return index;
}

// =================================================================
// Name: FSManager::WriteData
// Desc: Writes data to blocks specified by inode of file
// Args: string& data - the data to write to file
//       File* file - File to which data is being written
//       Inode* node - corresponding Inode of file
// =================================================================
void FSManager::WriteData(string& data, File *file, Inode* node)
{

    // While there is data to write, find the next block and write
	// data to it
	while (data.length() > 0)
    {

        int file_offset = file->GetSeekOffset();
        int block_index = file_offset / BLOCK_SIZE;
        int offset = file_offset % BLOCK_SIZE;
        IndirectBlock *iBlock;

        int block;

        if (file_offset < BLOCK_SIZE*NUM_DIRECT_LINKS)
        {
            // Do direct fetch
            block = node->GetBlockLocation(block_index);
        }
        else if (file_offset < BLOCK_SIZE*(NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS))
        {
            // Singly Indirect fetch
            block_index -= NUM_DIRECT_LINKS;
            iBlock = ReadIndirectBlock(node->GetBlockLocation(NUM_DIRECT_LINKS));
            block = iBlock->GetAddr(block_index);
            delete iBlock;
        } 
        else if (file_offset < BLOCK_SIZE*(NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS + NUM_DOUBLY_INDIRECT_LINKS))
        {
            // Doubly Indirect fetch
            block_index -= NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS;
            iBlock = ReadIndirectBlock(node->GetBlockLocation(NUM_DIRECT_LINKS+1));
            block = iBlock->GetAddr(block_index/NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
            iBlock = ReadIndirectBlock(block);
            block = iBlock->GetAddr(block_index % NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
        }
        else if (file_offset < BLOCK_SIZE*(NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS + NUM_DOUBLY_INDIRECT_LINKS + NUM_TRIPLY_INDIRECT_LINKS))
        {
            // Triply Indirect fetch
            block_index -= NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS + NUM_DOUBLY_INDIRECT_LINKS;
            iBlock = ReadIndirectBlock(node->GetBlockLocation(NUM_DIRECT_LINKS+2));
            block = iBlock->GetAddr(block_index/NUM_DOUBLY_INDIRECT_LINKS);
            delete iBlock;
            iBlock = ReadIndirectBlock(block);
            block = iBlock->GetAddr(block_index/NUM_SINGLY_INDIRECT_LINKS % NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
            iBlock = ReadIndirectBlock(block);
            block = iBlock->GetAddr(block_index % NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
        }
        else
        {
            cerr << "File too large for file system" << endl;
            exit(1);
        }
        
		// Calculate how much data is to be written and its location
		int bytesToWrite = min(BLOCK_SIZE-offset, (int)(data.length()));
		
		// Retrieve block from cache
        Block *cache_block = ReadCache(block);
        char buffer[BLOCK_SIZE];

        // If block is not yet in cache, write it to the cache
		if(cache_block == NULL){
            fseek(fp, sb->GetBlocksOffset() + block*BLOCK_SIZE, SEEK_SET);
            fread(buffer, 1, BLOCK_SIZE, fp);
            for(int i = offset; i < bytesToWrite + offset; i++){
                buffer[i] = data[i-offset];
            }
            cache_block = new Block(buffer);
        }
        // Otherwise update its value in the cache
		else{
            for(int i = offset; i < bytesToWrite + offset; i++){
                cache_block->SetByte(data[i-offset],i);
            }
        }

        // Write the block to the cache
		WriteCache(block, cache_block);

        // Write either rest of data or until block is full
        fseek(fp, sb->GetBlocksOffset() + block*BLOCK_SIZE + offset, SEEK_SET);
        fwrite(data.c_str(), 1, bytesToWrite, fp);
        data.erase(0, bytesToWrite);
        file->SetSeekOffset(file->GetSeekOffset()+bytesToWrite);

    }

}

// =================================================================
// Name: FSManager::ReadData
// Desc: Reads number of bytes from file into string
// Args: File* file - File object corresponding to data to read
//       Inode* node - Inode corresponding to file
//       int bytes - number of bytes to read from file
// =================================================================
string FSManager::ReadData(File *file, Inode* node, int bytes)
{

    string data = "";

    // Determine which block to read from while still bytes to read
	while (bytes > 0)
    {

        int file_offset = file->GetSeekOffset();
        int block_index = file_offset / BLOCK_SIZE;
        int offset = file_offset % BLOCK_SIZE;
        IndirectBlock *iBlock;

        int block;

        if (file_offset < BLOCK_SIZE*NUM_DIRECT_LINKS)
        {
            // Do direct fetch
            block = node->GetBlockLocation(block_index);
        }
        else if (file_offset < BLOCK_SIZE*(NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS))
        {
            // Singly Indirect fetch
            block_index -= NUM_DIRECT_LINKS;
            iBlock = ReadIndirectBlock(node->GetBlockLocation(NUM_DIRECT_LINKS));
            block = iBlock->GetAddr(block_index);
            delete iBlock;
        } 
        else if (file_offset < BLOCK_SIZE*(NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS + NUM_DOUBLY_INDIRECT_LINKS))
        {
            // Doubly Indirect fetch
            block_index -= NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS;
            iBlock = ReadIndirectBlock(node->GetBlockLocation(NUM_DIRECT_LINKS+1));
            block = iBlock->GetAddr(block_index/NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
            iBlock = ReadIndirectBlock(block);
            block = iBlock->GetAddr(block_index % NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
        }
        else if (file_offset < BLOCK_SIZE*(NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS + NUM_DOUBLY_INDIRECT_LINKS + NUM_TRIPLY_INDIRECT_LINKS))
        {
            // Triply Indirect fetch
            block_index -= NUM_DIRECT_LINKS + NUM_SINGLY_INDIRECT_LINKS + NUM_DOUBLY_INDIRECT_LINKS;
            iBlock = ReadIndirectBlock(node->GetBlockLocation(NUM_DIRECT_LINKS+2));
            block = iBlock->GetAddr(block_index/NUM_DOUBLY_INDIRECT_LINKS);
            delete iBlock;
            iBlock = ReadIndirectBlock(block);
            block = iBlock->GetAddr(block_index/NUM_SINGLY_INDIRECT_LINKS % NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
            iBlock = ReadIndirectBlock(block);
            block = iBlock->GetAddr(block_index % NUM_SINGLY_INDIRECT_LINKS);
            delete iBlock;
        }
        else
        {
            cerr << "File too large for file system" << endl;
            exit(1);
        }

        // Read either rest of data or until block is full
        Block *cache_block = ReadCache(block);
        char buffer[BLOCK_SIZE];
        int bytesToRead = min(BLOCK_SIZE-offset, bytes);


        // If not in cache, add to the cache
		if(cache_block == NULL){
            fseek(fp, sb->GetBlocksOffset() + block*BLOCK_SIZE, SEEK_SET);
            fread(buffer, 1, BLOCK_SIZE, fp);
            cache_block = new Block(buffer);
            WriteCache(block, cache_block);
        }
        
		// Read data from the cache
		for (int i = offset; i < bytesToRead + offset; i++) {
            data += cache_block->GetByte(i);
        }
        
		// Increment the seek offset based on how many bytes read
		file->SetSeekOffset(file->GetSeekOffset()+bytesToRead);
        bytes -= bytesToRead;
    }
    return data;
}

// =================================================================
// Name: FSManager::WriteFile
// Desc: Writes a file to disk
// Args: string data - data to write to file
//       File* file - file to which data should be written
//       bool isDir - whether the file is a directory
// =================================================================
void FSManager::WriteFile(string data, File *file, bool isDir)
{

    int inode_index = file->GetInodeIndex();

    Inode *node = ReadInode(inode_index);

    // Directory offset should always be 0
	if (isDir) {
        file->SetSeekOffset(0);
    }


    // Update the inode's size if necessary
    int size = data.length() + file->GetSeekOffset();
    if (node->GetSize() < size || isDir) {
        node->SetSize(size);
    }


    // Update the modified time
    node->SetModified(time(0));
    node->SetChanged(time(0));

    int num_blocks = ceil(size / (double)BLOCK_SIZE);
    node->SetNumBlocks(num_blocks);

    // Handle direct links
    int direct_links = NUM_DIRECT_LINKS;
    if (num_blocks < NUM_DIRECT_LINKS)
        direct_links = num_blocks;
    for (int i = 0; i < direct_links; i++)
    {
        if (node->GetBlockLocation(i) == -1)
        {
            int block_index = sb->FreeDataBlockPop();
            node->SetBlockLocation(i, block_index);
        }

        num_blocks--;

    }

    // If the data didn't fit into the direct link nodes
    if (num_blocks > 0)
    {
        int block_index = node->GetBlockLocation(NUM_DIRECT_LINKS);
        node->SetBlockLocation(NUM_DIRECT_LINKS, 
                MakeSinglyIndirect(block_index, num_blocks));
    }

    // If the data didn't fit into the direct and singly indirect nodes
    if (num_blocks > 0)
    {
        int block_index = node->GetBlockLocation(NUM_DIRECT_LINKS+1);
        node->SetBlockLocation(NUM_DIRECT_LINKS+1, 
                MakeDoublyIndirect(block_index, num_blocks));
    }

    // If the data didn't fit into the direct, singly, and doubly linked nodes
    if (num_blocks > 0)
    {
        int block_index = node->GetBlockLocation(NUM_DIRECT_LINKS+2);
        node->SetBlockLocation(NUM_DIRECT_LINKS+2, 
                MakeTriplyIndirect(block_index, num_blocks));
    }

    // Write Inode to file
    WriteInode(node, inode_index);

    // Write data to file
    WriteData(data, file, node); 

    delete node;
}

// =================================================================
// Name: FSManager::ReadFile
// Desc: Reads a file on the disk
// Args: File* file - file to read from
//       int bytes - number of bytes to read from file
// =================================================================
string FSManager::ReadFile(File *file, int bytes)
{
    int inode_index = file->GetInodeIndex();
    string data;

    Inode *node = ReadInode(inode_index);
    node->SetAccessed(time(0));

    // Update the inode's size if necessary
    int size = bytes + file->GetSeekOffset();
    if (node->GetSize() < size) {
        node->SetSize(size);
    }

    if (bytes + file->GetSeekOffset() > size) {
        cerr << "Attempting to read more bytes than file contains" << endl;
        return NULL;
    }

    data = ReadData(file, node, bytes);

    WriteInode(node, inode_index);

    delete node;

    return data;
}
